|
In computer programming, the XOR swap is an algorithm that uses the XOR bitwise operation to swap values of distinct variables having the same data type without using a temporary variable. "Distinct" means that the variables are stored at different memory addresses; the actual values of the variables do not have to be different. ==The algorithm== Conventional swapping requires the use of a temporary storage variable. Using the XOR swap algorithm, however, no temporary storage is needed. The algorithm is as follows:〔(【引用サイトリンク】title=Swapping Values with XOR )〕 X := X XOR Y Y := X XOR Y X := X XOR Y The algorithm typically corresponds to three machine code instructions. Since XOR is a commutative operation, X XOR Y can be replaced with Y XOR X in any of the lines. When coded in assembly language, this commutativity is often exercised in the second line: In the above System/370 assembly code sample, R1 and R2 are distinct registers, and each XR operation leaves its result in the register named in the first argument. Using x86 assembly, values X and Y are in registers eax and ebx (respectively), and places the result of the operation in the first register. However, the algorithm fails if ''x'' and ''y'' use the same storage location, since the value stored in that location will be zeroed out by the first XOR instruction, and then remain zero; it will not be "swapped with itself". Note that this is ''not'' the same as if ''x'' and ''y'' have the same values. The trouble only comes when ''x'' and ''y'' use the same storage location, in which case their values must already be equal. That is, if ''x'' and ''y'' use the same storage location, then the line: X := X XOR Y sets ''x'' to zero (because ''x'' = ''y'' so X XOR Y is zero) ''and'' sets ''y'' to zero (since it uses the same storage location), causing ''x'' and ''y'' to lose their original values. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「XOR swap algorithm」の詳細全文を読む スポンサード リンク
|